1. Field of the Invention
This invention relates to an apparatus and method for processing data in response to a sequence of program instructions at least one of which may be subject to cancellation.
2. Description of the Prior Art
In some pipelined CPUs an instruction can be cancelled before the point at which it would usually have finished. One condition which causes this behaviour is a memory access fault otherwise known as an abort. An abort is signaled when some intervention by the operating system is required. e.g. in a demand paged virtual memory system an abort is signaled when an attempt is made to access data which does not currently reside in the main memory of the system. Only after the operating system has moved the data into memory can the access be completed.
Typically an abort will simply cause the instruction which aborted to be cancelled and the instruction stream to be changed to execute a software abort handler. Once the abort handler has fixed the cause of the abort the instruction stream is switched back to the aborted instruction which will be re-executed.
As the aborted instruction has been partially executed before the abort is signaled and it was cancelled, it is vital that any state which the instruction has updated before the abort occurred does not prevent correct re-execution of the instruction.
For example, many instruction sets include instructions which load a register from an address calculated by summing the contents of a register holding a base address and a register holding a offset address. Often there is an option to write back to the register holding the base address the sum of its original contents plus the contents of the offset address. In this case the instruction will write to both the loaded register and the base register. In the event that a load aborts, the correct data is not available to be written into the loaded register. However, incorrect data can safely be written as it will be replaced by the correct value when the instruction is re-executed.
The same is not, however, true for the write to the base register. The base address register is read by the instruction as well as written by it, so when the instruction is re-executed it must contain the original value or the load will occur from the wrong address. Although the signal that an access has aborted is often a late arriving signal, in most systems it does arrive in time for the base register write to be averted.
Another example is concerned with instruction sets that include a load-multiple instruction which will load a set of registers from consecutive memory locations starting from an address specified in a base register. Often these instructions take many cycle to execute as they load data into successive registers in the specified set.
In some systems it is possible for an abort to occur on any of the accesses caused by the instruction. Normally this does not cause any additional difficulty as all the registers can be safely reloaded upon re-execution of the instruction. However at least two potentially difficult cases do exist:
a) the base writeback case analogous to the previous example;
b) the base register is also a member of the set of registers which is to be loadedxe2x80x94in this case the load to the base register may occur several cycles before an abort happens on a latter member of the set of registers to be loaded.
Case (a) is typically dealt with by delaying the base register writeback until it is know that no further aborts can occur for the instruction. If an abort does occur then the writeback is cancelled.
It is harder to deal with case (b) in the same manner as this would require that the order of the loads was shuffled to make the base register load occur last of all. One more practical way to deal with case (b) is to provide dedicated hardware to preserve a copy of the original base register upon starting the instruction up to a point where an abort can no longer occur. This copy is used to restore the original value if an abort does occur.
A problem with this approach is that the dedicated hardware tends to disadvantageously increase the circuit size and complexity.
It should be noted that the situations detailed above are merely examples and that similar problems may occur with other instructions as well as loads and for other cancellations as well as aborts.
Viewed from one aspect the present invention provides an apparatus for processing data in response to a sequence of program instructions, said apparatus comprising: a primary pipelined processing unit for performing data processing, said primary pipelined processing unit being responsive to a cancellation condition to cancel processing of a partially completed cancellable program instruction; a fix-up pipelined processing unit; and a pseudo instruction generator responsive to at least one cancellable program instruction that can be subject to cancellation to generate a cancellation fix-up instruction that is issued to said fix-up pipelined processing unit, said cancellation fix-up instruction being operable upon occurrence of a cancellation condition to control said fix-up pipelined processing unit to produce a state in which said partially completed program cancellable instruction may be re-executed at a later time.
The apparatus of the present invention recognises the above problem and addresses the problem by providing an apparatus to handle cancellation of program instructions and to restore the apparatus to a state in which the program instruction can be re-executed without, for example, storing the original value of the base address in separate specially provided and controlled hardware. It does this by using a pseudo-instruction to deal with cancellation, the pseudo-instruction being fed down a pipeline of a fix-up processing unit in the same way as any other instruction. This means that much of the interlock and forwarding logic of the pipelined processor can be re-used to handle cancellation thereby reducing the need for dedicated special purpose logic. Thus, if an abort occurs the normal instruction will be cancelled, while the fix up pseudo instruction will only complete in such a case.
The advantages of the present invention become greater as machines are adapted to launch more instructions at once and do more out of order execution. In such machines a cancellation fix-up pseudo-instruction allows almost the same hardware which deals with execution order and forwarding for standard instructions to deal with keeping the cancellation fix-up in the right place in the order. This would otherwise become an increasingly difficult task for dedicated special purpose hardware.
Advantageously, said pseudo instruction generator is operable to generate a fix-up instruction only when said cancellable program instruction comprises an instruction to overwrite the contents of a base register containing a base address for a data processing operation specified by said cancellable instruction.
Many instructions that are cancelled when partially completed can simply be re-executed without any problems. With other instructions which involve the changing of a value in the base register which is used as an address in the instruction re-execution of a partially completed instruction may give the wrong result as the base address register which is used by the instruction may have been changed. By differentiating between these two sets of instructions and only producing a fix-up instruction in the cases where re-execution may be a problem, this embodiment of the present invention provides an efficient way of dealing with these different situations.
In preferred embodiments, said pseudo instruction generator is operable in response to a cancellable program instruction that overwrites the contents of a base register containing a base address for a data processing operation specified by said cancellable instruction to generate a cancellation fix-up instruction that reads an initial value from said base register prior to it being overwritten.
By issuing a pseudo instruction to read the base address such embodiments can restore the apparatus to its original state even in the case of a cancellation to an instruction occurring after the base address storage means has been overwritten. The use of the pseudo instruction to read the base address storage means results in the value travelling down the pipeline in the fix-up processing unit with the pseudo instruction thereby obviating the need for a special register and control logic to store the value.
In some embodiments if said cancellable instruction is one that calculates a writeback value to be stored in said base register, then a completion writeback instruction is generated that controls said fix-up pipelined processing unit to calculate said writeback value and to only perform said writeback to said base register upon detection that cancellation conditions for said at least one program instruction are no longer possible.
A writeback instruction is an instruction that writes the base address register with the result of the address calculated by a memory operation with base-register-update. By permitting the writeback to occur after it is established that no early termination of the program instruction will occur, any delay associated with the deferring of the writeback can be reduced.
In preferred embodiments of the invention program instructions that both overwrite the contents of a base register and calculate a writeback value to said base register are not permitted such that said fix-up pipelined processing unit is available to process either a cancellation fix-up instruction that reads an initial value of a completion writeback instruction that calculates a writeback value.
Not permitting program instructions that overwrite the contents of a base register and that calculate a writeback value to that base register avoids potentially damaging register write conflicts and has the result that the fix-up pipelined processing unit will be available to handle either the cancellation fix-up instruction or the completion writeback instruction.
In the case where the program instruction to overwrite said base address storage means is an instruction that needs to be fully completed before it is known if a cancellation condition will occur or not, said cancellation fix-up instruction is operable to overwrite said base register with said initial value in response to detection of said cancellation condition.
The use of the pseudo instruction to restore the base address value to its original value means that the pipeline logic needs little alteration to handle cancellations, such as aborts, that occur after the base address has been overwritten.
Advantageously, upon detection that no cancellation of said cancellable program instruction will occur, said cancellation fix-up instruction is cancelled.
The cancellation of the fix-up instruction at this point means that the fix-up processing unit can advance to the next instruction; the fix-up instruction having had no effect on the processor state.
Embodiments of the present invention are particularly well suited to alleviate cancellation problems associated with block memory access instructions and, in particular, block loads from memory that include a base address writeback or where the base address register is in the load list and/or block stores to memory including a base address writeback.
In such cases, the primary pipelined processing unit may be a load store unit and the fix-up pipelined processing unit may be an arithmetic logic unit, that may also calculates any writeback address. In other embodiments the fix-up unit may be a different type of execution unit.
In some embodiments said primary pipelined processing unit comprises said fix-up pipelined processing unit, whereas in other embodiments, such as in superscaler systems, the two units are separate units and the fixed up unit is not special hardware but is any execution unit that is available at the time now.
In preferred embodiments, if said cancellable program instruction is a block memory access instruction to memory locations specified by a base address value stored in a base address register and said cancellable program instruction does not involve writing to said base register, then said cancellation fix-up instruction is a no-operation instruction, said no-operation instruction serving to prevent subsequent instructions from being executed by said apparatus until the abort status of said block memory access instruction is resolved.
Although it would be possible that when the program instruction does not instruct the overwriting of the base address register the fix-up pipelined processing unit could be used for other calculations, it is preferred that a NOP instruction is entered into the fix-up pipelined processing unit as this reduces any alterations required to the interlock and forwarding logic. Furthermore, by having different pseudo-instructions for different situations, the decoder can behave in the same way for all these cases. This helps keep the decoder simple and fast.
Advantageously said pseudo-instruction generator is operable to issue said fix-up instruction to said fix-up pipelined processing unit at the same time that said primary pipelined processing unit receives a data processing instruction.
Thus, the instructions run in parallel down their respective pipelines simplifying the control of the system.
Although the apparatus of the present invention can respond to any cancellation condition it is particularly well adapted to handle aborts.
A further aspect of the present invention provides a method of processing data in response to a sequence of program instructions, comprising the steps of: issuing a cancellable program instruction that can be subject to cancellation to a primary pipelined processing unit for performing data processing, said primary pipelined processing unit being responsive to a cancellation condition to cancel processing of a partially completed cancellable program instruction; generating a cancellation fix-up instruction with a pseudo instruction generator in response to said cancellable program instruction and issuing said cancellation fix-up instruction to a fix-up pipelined processing unit, said cancellation fix-up instruction being operable upon occurrence of a cancellation condition to control said fix-up pipelined processing unit to produce a state in which said partially completed cancellable program instruction may be re-executed at a later time.